"""计算逆序数"""

import numpy as np
import time


class InvertedOrderNumber(object):
    """计算逆序数"""

    def __init__(self):
        self.data = []
        self.data_copy = []
        self.invert_order_number = 0

    def random_data(self, size, low=0, high=100):
        """随机数据"""
        self.data = np.random.randint(low, high, size).tolist()

    def compute(self):
        count = 0  # 初始逆序数

        def merge(arr, first, mid, last):
            nonlocal count
            i = first
            j = mid + 1
            tmp = []

            while i <= mid and j <= last:
                if arr[i] <= arr[j]:
                    tmp.append(arr[i])
                    i += 1
                else:
                    tmp.append(arr[j])
                    j += 1
                    count += mid - i + 1

            while i <= mid:
                tmp.append(arr[i])
                i += 1

            while j <= last:
                tmp.append(arr[j])
                j += 1

            cur = first
            while cur <= last:
                arr[cur] = tmp[cur - first]
                cur += 1

        def merge_sort(arr, first, last):
            if first == last:
                return
            mid = (first + last) // 2

            merge_sort(arr, first, mid)
            merge_sort(arr, mid + 1, last)
            merge(arr, first, mid, last)

        data_copy = self.data.copy()
        merge_sort(data_copy, 0, len(self.data) - 1)
        self.invert_order_number = count
        self.data_copy = data_copy

    def print(self):
        print("随机数据: ", ', '.join(str(x) for x in self.data))
        print("排序后数据: ", ', '.join(str(x) for x in self.data_copy))
        print("逆序数: ", self.invert_order_number)


if __name__ == '__main__':
    ins = InvertedOrderNumber()
    ins.random_data(300)

    start = time.time()
    ins.compute()
    end = time.time()
    print("用时{0:f}微秒".format((end - start) * 1000 * 1000))

    ins.print()
